class Solution:
    def f(self,n):
        if n in self.f_value:
            return self.f_value[n]
        if n==0:
            self.f_value[0]=0
        if n==1:
            self.f_value[1]=1
        if n%2==0:
            self.f_value[n]=self.f(n//2)
        if n%2==1:
            self.f_value[n]=self.f(n//2)+self.f(n//2+1)
        return self.f_value[n]

    def getMaximumGenerated(self, n: int) -> int:
        self.f_value={}
        max=0
        for i in range(n+1):
            if max<self.f(i):
                max=self.f(i)
        return max

